%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graphbook/
%%
%% Copyright (C) 2009--2013 Minh Van Nguyen <mvngu.name@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{algorithmic}[1]
%% input and output
\Require A weighted graph or digraph $G = (V, E)$, where the vertices
  are numbered as $V = \{1, 2, \dots, n\}$. A starting vertex $s$.
\Ensure A list $D$ of distances from $s$ to all other vertices. A list
  $P$ of parent vertices such that $P[v]$ is the parent of $v$.
%%
%% algorithm body
\State $D \assign [\infty, \infty, \dots, \infty]$\Comment{$n$ copies of $\infty$}
\State $C \assign$ list of candidate vertices to visit
\While{$\length(C) > 0$}
  \State select $v \in C$
  \State $C \assign \remove(C, v)$
  \For{\rm each $u \in \adj(v)$\label{alg:generic_shortest_path:neighbors}}
    \If{$D[u] > D[v] + w(vu)$}
      \State $D[u] \assign D[v] + w(vu)$
      \State $P[u] \assign v$
      \If{$u \notin C$}
        \State add $u$ to $C$
      \EndIf
    \EndIf
  \EndFor
\EndWhile
\State \Return $(D,P)$
\end{algorithmic}
